What W. W. Peterson said in Scientific American in 1962, “Error-free performance is the goal of every good communication system,” is still a truism. Yet, in the global business model, there is an emergence of fundamentally different, malicious attacks that: a) modify designs, b) tamper with hardware, and c) contain spoofed software in mission- and safety-critical systems. In the past conventional error detection and correction (EDAC) techniques have largely been adequate to satisfy a specified probability of undetected (random) error threshold for data transfers, particularly when protecting boot firmware in embedded systems. However, in today's marketplace, additional fortification of these algorithms is needed to address the identification, integrity and security issues of outsourced system development and data delivery. The problem of detecting, correcting, tracing, or countering a deliberate corruption of systems and data due to a cyber attack is of particular concern. Peterson talked of protection from “noise,” yet, today we must include protection from intelligent attacks, in critical environments. These critical environments must be fortified to survive through the loss of physical security. Litanies of techniques have been tailored to various levels of need. Generally, encryption is used to secure most critical data, but there is a niche need for data protection (or tamper detection) through systematic encoding that doesn't utilize encryption. Some dual-redundant systems have stringent real-time startup and response requirements. Any extension to EDAC processing or additional security algorithms to address malicious attacks must still meet the timing requirements.
In response to potential boot firmware security breaches, some computing devices provide security measures to ensure that the boot firmware comes from a trusted source. These security measures rely on digital signatures, which uniquely identify the source of the associated boot firmware. The computing device can decode a digital signature to identify the firmware and accept or reject the boot based on the comparison of the signature to a known value. The difficulty with this approach when there is a malicious attack on the design, is that the known value can easily be modified to provide a match to the calculated value. Other deficits would be of a computing device that only verifies the firmware once after installation, or only at boot time. After the boot, the firmware is assumed to not have been altered dynamically. These threats aren't prevented by passive security measures.
Advances in error control coding have enabled their use to be ubiquitous in digital information storage and transfer. Examples of this digital information include phones, the internet, DVDs, electronic commercial transactions, disk drives, ISBN numbers, UPC codes, and RFID tags.
The generalized abstraction of the parts of error control coding are given in the prior art. In a basic example of the prior art, FIG. 1-a, source data enters an EDAC encoder, and after encoding, it is then transmitted or transferred over a channel. On the data sink end, after the channel, the encoded data is checked for errors by the EDAC decoder. One type of system, using this basic design, responds with a retry request if an error is detected. In another type, errors are corrected by the decoder. Both types of systems have limits on the number and type of errors that are detectable, correctable, undetectable, and uncorrectable. These types of EDAC systems are not designed, in general, to provide protection from cyber attacks, but are designed to handle random or burst errors, or some combination of random and burst errors.
The prior art of FIG. 1-b adds data security by adding encryption encoding and decoding. Some performance and size limits are improved by preceding the encryption with a compression stage, as is well known in the art. Typically these steps are much more time intensive than just the EDAC stage, and impractical in some real-time embedded systems for the associated risk.
More examples in the art exist that show variations to the basic example mentioned and to the more complex example, or combinations through concatenation, interleaving, redundancy, and feedback. The use of these variations has led to disk drives boasting of probabilities of undetected errors, after error correction, on the order of 10−18.
Some applications require very low probabilities of undetected errors. For the most critical avionics applications, there are requirements of undetected error probabilities of 10−9, plus no single point of failure, and no common cause for hardware systems. For a similar critical software system, it would be required to satisfy what is called “Level A” objectives, rather than the 10−9, but still satisfy the other requirements.
It has been pointed out that there are potential gaps in the level of protection from cyber attack in the end-to-end life cycle of critical avionics software systems. The solution to protecting the gaps has been the dependability of the EDAC encoder remainder, attached to the boot code image, 902, at development time, see FIG. 7 904.
Additional mitigation procedures are necessary when it is assumed that the strong protections provided in the various physical layers and devices will result in adequate end-to-end protection of data, from emerging threats at higher levels, for the data's life cycle. A practical partial solution, again, is to attach sufficient protection to the data at the source and let it remain attached for the data's lifespan, checking it along the way. As mentioned this sole reliance on EDACs for protection is no longer sufficient for critical systems, in light of the new threats, but any solution has to be simple, cheap, adequate, and fast, as always.
In U.S. Pat. No. 3,786,439, issued on Jan. 15, 1974, McDonald introduced the novel idea, “Error detection is enhanced by using multiple independent error codes combined with non-linear changes in the data field as applied to different error codes.” It is then said to use a non-linear permutation by “scrambling track-to-error code relationships between a plurality of independent codes.” The definition of non-linear is not explicitly defined, but later in the discussion it seems to mean not to do a cyclic permutation. It indicates breaking the data set into subsets with one ECC-3 covering all data end-to-end in the statements “ . . . generate a second non-linearly related data field” and “with the non-linear difference between the two codes, a high degree of reliability is provided in that the probability of an error condition residing in the same mathematical subfield of the two codes becomes highly remote.” Later, it is stated that each of the polynomials has an 1+x term. In the claims, following the methods would indicate “a third set of errors less than the first and second sets by including errors not in said first and second sets . . . ”
Following McDonald, in U.S. Pat. No. 5,392,299, issued on Feb. 21, 1995, Rhines et al., introduces the idea of an triple orthogonally interleaved error correction system. The system is for random & burst enhanced protection tailored to the channel at hand. The scrambling is fixed and the method requires an orthogonal interleaving of three parts. The definition of orthogonal is a ‘shuffling’ to enhance the protection against burst errors. Later it states that it is well known in the art to employ an interleaving process either before or after encoding to provide additional protection against included errors. The interleaving is defined to be a process where consecutive bytes are separated from each other, to protect against burst errors.
In U.S. Pat. No. 5,673,316, issued on Sep. 30, 1997, Auerbach et al. discuss the creation and distribution of a cryptographic envelope that is an aggregation of information parts, where each of the parts to be protected are encrypted.
In the abstract of “Factoring Large Numbers with the TWINKLE Device,” Adi Shamir states “The security of the RSA public key cryptosystem depends on the difficulty of factoring a large number n which is the product of two equal size primes p and q. He also states “The current record in factoring large RSA keys is the factorization of a 465 bit number . . . [The TWINKLE] technique can increase the size of factorable numbers by 100 to 200 bits . . . ” and that “ . . . can make 512 bit RSA keys (which protect 95% of today's E-commerce on the Internet very vulnerable.”
In the 1996 paper by Berrou, it states “2) Non uniform interleaving: It is obvious that patterns giving the shortest distances, such as those represented in FIG. 5, can be ‘broken’ by appropriate non uniform interleaving, in order to transform a separable FC [Finite Codeword—finite distance from 0] pattern into either a non separable or a non FC.” “Non uniform interleaving must satisfy two main conditions: the maximum scattering of data, as in usual interleaving, and the maximum disorder in the interleaved data sequence. The latter, which may be in conflict with the former, is to make redundancy generation by the two encoders as diverse as possible.”